package character

import (
	"crypto/md5"
	"encoding/hex"
	"fmt"
)

func main() {
	trie := &Trie{}
	trieTree := trie.NewTrie()
	strs := []string{"释雨", "Summer", "Rain", "释雨的博客", "Blog"}
	for _, str := range strs {
		trieTree.Insert(str)
	}

	if trieTree.Select("释雨的笔记本") {
		fmt.Println("yes")
	} else {
		fmt.Println("no")
	}

}

//Trie树，也叫前缀树或字典树，是利用字符串之间的公共前缀，将重复的前缀合并在一起，组成的一个树形结构，
//专门用于处理字符串匹配，用来解决在一组字符串集合中快速查找某个字符串的问题。
//通常，我们可以通过 Trie 树来构建敏感词或关键词匹配系统。
type Trie struct {
	Root *TrieNode
	Ptr  *TrieNode
}

type TrieNode struct {
	Data     string
	Children map[string]*TrieNode
	IsEnd    bool
}

func (t *Trie) NewTrie() *Trie {
	root := &TrieNode{Data: "/"}
	return &Trie{Root: root, Ptr: root}
}

// 往Trie树中插入一个字符串，
//时间复杂度：O(n) n为插入的字符串的长度
func (t *Trie) Insert(str string) {
	strRune := []rune(str)
	n := len(strRune)
	triePtr := t.Ptr
	trieNode := &TrieNode{}
	Md5Inst := md5.New()
	var index string
	for i := 0; i < n; i++ {
		trieNode.Data = string(strRune[i : i+1])
		Md5Inst.Write([]byte(trieNode.Data))
		index = hex.EncodeToString(Md5Inst.Sum(nil))
		// map 得初始化才能使用
		if triePtr.Children == nil {
			triePtr.Children = make(map[string]*TrieNode)
		}
		if triePtr.Children[index] == nil {
			triePtr.Children[index] = trieNode
		}
		triePtr = trieNode
	}
	trieNode.IsEnd = true
}

//查找一个字符串是否存在于Trie树中
//时间复杂度：O(k) k为要查找的字符串的长度
func (t *Trie) Select(str string) bool {
	strRune := []rune(str)
	n := len(strRune)
	triePtr := t.Ptr
	Md5Inst := md5.New()
	var data string
	var index string
	for i := 0; i < n; i++ {
		// fmt.Println(triePtr)
		data = string(strRune[i : i+1])
		Md5Inst.Write([]byte(data))
		index = hex.EncodeToString(Md5Inst.Sum(nil))
		if triePtr.Children[index] == nil {
			return false
		}
		triePtr = triePtr.Children[index]
	}
	if !triePtr.IsEnd {
		return false
	}
	return true
}
